package huawei;

import java.util.Arrays;

/**
 * @author: yfq
 * @date: 2023/3/13 9:51
 * @description:
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 3, 2, 1};
        sort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int start, int end) {
        if (start < end) {
            int partition = partition(arr, start, end);

            sort(arr, start, partition - 1);

            sort(arr, partition + 1, end);
        }
    }

    public static int partition(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        int temp = arr[start];
        while (i < j) {
            while (i < j && arr[j] >= temp) {
                j--;
            }
            arr[i] = arr[j];

            while (i < j && arr[i] <= temp) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;

        return i;
    }
}
